package work;

/**
 * 合并两个有序链表
 */
public class MergeTwoLists {
    //时间复杂度：O(n)
    //思路：1）使用帮助节点；2）比较节点
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode protect = new ListNode(0);//帮助节点
        ListNode temp = protect;
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }else{
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    temp.next = l1;
                    l1 = l1.next;
                }else{
                    temp.next = l2;
                    l2 = l2.next;
                }
                temp = temp.next;
            }
        }

        temp.next = l1 != null ? l1 : l2;
        return protect.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, null));
        ListNode l2 = new ListNode(3, new ListNode(4, null));

        ListNode result = mergeTwoLists(l1, l2);
        while(result != null){
            System.out.print(result.val + " ===>");
            result = result.next;
        }
    }
}
class ListNode{
    int val;
    ListNode next;

    public ListNode(){}
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val, ListNode next){
        this(val);
        this.next = next;
    }
}
